"""
题目：用递归解决汉诺塔问题（将 n 个盘子从 A 柱移到 C 柱，中间可借助 B 柱，每次只能移一个盘子，且大盘不能压小盘）。
"""

def hanoi(n, source, auxiliary, target):
    """
    递归解决汉诺塔问题
    :param n: 盘子数量
    :param source: 源柱子
    :param auxiliary: 辅助柱子
    :param target: 目标柱子
    """
    # 基线条件：只有1个盘子时，直接从源柱移到目标柱
    if n == 1:
        print(f"移动盘子1从{source}到{target}")
        return
    # 步骤1：将n-1个盘子从源柱移到辅助柱（借助目标柱）
    hanoi(n - 1, source, target, auxiliary)
    # 步骤2：将第n个盘子从源柱移到目标柱
    print(f"移动盘子{n}从{source}到{target}")
    # 步骤3：将n-1个盘子从辅助柱移到目标柱（借助源柱）
    hanoi(n - 1, auxiliary, source, target)

# 测试
if __name__ == "__main__":
    print("3个盘子的汉诺塔移动步骤：")
    hanoi(3, 'A', 'B', 'C')
    # 输出：
    # 移动盘子1从A到C
    # 移动盘子2从A到B
    # 移动盘子1从C到B
    # 移动盘子3从A到C
    # 移动盘子1从B到A
    # 移动盘子2从B到C
    # 移动盘子1从A到C